#include <bits/stdc++.h>

using namespace std;

// 最大频率栈
// 测试链接 : https://leetcode.cn/problems/maximum-frequency-stack/

class FreqStack 
{
private:
    // 出现的最大次数
    int topTimes = 0;
    // 每一个数出现了几次
    unordered_map<int, int> valueTimes;
    // 每层节点
    unordered_map<int, list<int>> cntValues;

public:
    void push(int val) 
    {
        int curTopTimes = ++valueTimes[val];
        cntValues[curTopTimes].emplace_back(val);
        // 看看这个元素的出现频率能不能推高最大出现频率
        topTimes = max(topTimes, curTopTimes);
    }
    
    int pop() 
    {
        list<int>& topTimeValues = cntValues[topTimes];
        int ans = topTimeValues.back(); // 获取出现频率最高且离栈顶最近的元素
        topTimeValues.pop_back(); // 将该元素从最大频率栈中删除
        if(topTimeValues.empty()) cntValues.erase(topTimes--); // 最大频率栈中没有元素了
        --valueTimes[ans];
        if(valueTimes[ans] == 0) valueTimes.erase(ans); // 这里可以不进行删除，因为没有查询的操作
        return ans;
    }
};

// 做法二见灵神题解，题解链接如下：
// https://leetcode.cn/problems/maximum-frequency-stack/solutions/1998430/mei-xiang-ming-bai-yi-ge-dong-hua-miao-d-oich/
class FreqStack 
{
    unordered_map<int, int> cnt;
    vector<stack<int>> stacks; // stacks 的 size 就表示最大出现频率

public:
    void push(int val) 
    {
        // 这个元素的频率已经是目前最多的，现在又出现了一次
        if(cnt[val] == stacks.size()) 
        {
            // 那么必须创建一个新栈，这个栈就是最大频率栈，存在出现频率最多的数
            stacks.push_back({});
        }
        stacks[cnt[val]].push(val);
        ++cnt[val];
    }
    
    int pop() 
    {
        int val = stacks.back().top(); // 弹出最大频率栈的栈顶元素
        stacks.back().pop();
        // 最大频率栈为空，则需要将最大频率栈去除掉，这样才能正确地维护最大出现频率
        if(stacks.back().empty()) stacks.pop_back();
        --cnt[val];
        return val;
    }
};